import S0502
def getNext(part):
    next=[-1]
    j=-1
    i=0
    while i<len(part)-1:
        #print("j==",j,",i==",i)
        if part[j]==part[i] or j==-1:
            j=j+1
            i=i+1
            next.append(j)
        else:
            j=next[j]
    return next
def kmp(txt,part):
    next=getNext(part)
    i=0
    j=0
    while i<len(txt)-1:
        
        if txt[i]==part[j] or j==-1:
            i=i+1
            j=j+1
        else:
            j=next[j]
        if j==len(part):
            return i-j
    return -1
#tmp=getNext('ababc')
tmp=getNext('abaabc')
print(tmp)

# tmp=S0502.getNext('ababaaababaa')
# print(tmp)

index=kmp('abaabaabacacaabaabcc','abaabc') 
print(index)

index=S0502.kmpIndex('abaabaabacacaabaabcc','abaabc') 
print(index)